By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 34, Issue 2, pp. 261-513

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles

Joshua Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, and Ashish Sabharwal

pp. 261-276

BibTeX  Abstract Full Text:  PDF

A Complete Characterization of the Algebras of Minimal Bilinear Complexity

Markus Bläser

pp. 277-298

BibTeX  Abstract Full Text:  PDF

Nonindependent Randomized Rounding and an Application to Digital Halftoning

Benjamin Doerr

pp. 299-317

BibTeX  Abstract Full Text:  PDF

Instability of FIFO at Arbitrarily Low Rates in the Adversarial Queueing Model

Rajat Bhattacharjee, Ashish Goel, and Zvi Lotker

pp. 318-332

BibTeX  Abstract Full Text:  PDF

Generalized Irreducibility of Consensus and the Equivalence of t-Resilient and Wait-Free Implementations of Consensus

Tushar Chandra, Vassos Hadzilacos, Prasad Jayanti, and Sam Toueg

pp. 333-357

BibTeX  Abstract Full Text:  PDF

Approximation Algorithms for the 0-Extension Problem

Gruia Calinescu, Howard Karloff, and Yuval Rabani

pp. 358-372

BibTeX  Abstract Full Text:  PDF

An Optimal Algorithm for the Maximum-Density Segment Problem

Kai-min Chung and Hsueh-I Lu

pp. 373-387

BibTeX  Abstract Full Text:  PDF

New Approximation Techniques for Some Linear Ordering Problems

Satish Rao and Andréa W. Richa

pp. 388-404

BibTeX  Abstract Full Text:  PDF

Quick k-Median, k-Center, and Facility Location for Sparse Graphs

Mikkel Thorup

pp. 405-432

BibTeX  Abstract Full Text:  PDF

Online Scheduling to Minimize Average Stretch

S. Muthukrishnan, Rajmohan Rajaraman, Anthony Shaheen, and Johannes E. Gehrke

pp. 433-452

BibTeX  Abstract Full Text:  PDF

Traveling with a Pez Dispenser (or, Routing Issues in MPLS)

Anupam Gupta, Amit Kumar, and Rajeev Rastogi

pp. 453-474

BibTeX  Abstract Full Text:  PDF

The Simplex Algorithm in Dimension Three

Volker Kaibel, Rafael Mechtel, Micha Sharir, and Günter M. Ziegler

pp. 475-497

BibTeX  Abstract Full Text:  PDF

Temporal Reasoning about Two Concurrent Sequences of Events

Yasunori Ishihara, Shin Ishii, Hiroyuki Seki, and Minoru Ito

pp. 498-513

BibTeX  Abstract Full Text:  PDF